Online Judge►Google Code Jam

[Google Code Jam] 2015 - Qualification Round

題目每次都理解錯誤，是英文太差還是理解能力太差。

Problem A. Standing Ovation

題意

現在有一列觀眾，每個觀眾有自己的害羞指數，也就是必須得先有i個人拍手他才會拍手，為了讓拍手不中斷，請算出最少需要插入的人數。

解法

將差值補齊即可。

心得

首先題目就看錯了，看了許久才知道題目的意思，程式又一直寫不好，最後改個最笨的方法將多餘的人都往後排。

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
	fstream fin("in.txt",ios::in);
	fstream fout("out.txt",ios::out);
	int n ;
	fin >> n ;
	for ( int n2 = 0 ; n2 < n ; n2 ++ ){
		if ( n2 > 0 )
			fout << endl ;
		string input ;
		int number ;
		fin >> number ;
		fin >> input ;
		int count1[2000]  ;
		for ( int i = 0 ; i < number+1 ; i ++ )
			count1[i] = 0 ;
		int addnum  = 0 ;
		for ( int i = 0 ; i < number+1  ; i ++ )
			count1[i] = (int)input[i] - 48 ;
		for ( int i = 0 ; i < number  ; i ++ ){
			if ( count1[i] == 0 )
				addnum ++ ;
			else if ( count1[i] > 1 ){
				count1[i+1] += count1[i] - 1 ;
			}
		}
		fout << "Case #" << n2 + 1 << ": " << addnum ;
	}
	return 0;
}

Problem B. Infinite House of Pancakes

題意

現在有無限多個人要吃鬆餅，身為主人你可以任意將某人的鬆餅拿一個或多個分給另一個人，但在拿取的時間大家都不能吃，其它時候大家都會一起吃掉手上的一塊，請算出所需的最少時間。

解法

從最大值往下搜尋，搜尋每個人要分成每堆i個所需的移動數且加上i，最後就會得到最佳解。

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <fstream>
#include <cmath>
#include <limits.h>
using namespace std;
int main()
{
	fstream fin("in.txt",ios::in);
	fstream fout("out.txt",ios::out);
	int n ;
	fin >> n ;
	for ( int n2 = 0 ; n2 < n ; n2 ++ ){
		if ( n2 > 0 )
			fout << endl ;
		int number , max1 = 0 , array1[2000] , maxindex = 0 ;
		fin >> number ;
		int sum = 0 ;
		for ( int i = 0 , num ; i < number ; i ++ ){
			fin >> num ;
			array1[i] = num ;
			max1 = max(max1,num) ;
		}
		int min1 = max1 ;
		for ( int i = max1 - 1 ; i > 0  ; i -- ){
			int count_move = 0 ;
			double d1 = i ;
			for ( int j = 0 ; j < number ; j++ ){
				if ( array1[j] > i ){
					double d2 = array1[j] ;
					double result = ceil(d2/d1) ;
					int r = (int)result ;
					count_move += r - 1 ;
				}
			}
			min1 = min(min1,i+count_move) ;
		}
		fout << "Case #" << n2 + 1 << ": " << min1 ;
	}
	return 0;
}

另外兩題大測資錯了，稍為寫一下想法。

Problem C. Dijkstra

題意

請判斷字串是否能轉換成(i)(j)(k)的型式。

想法

必須轉換的過程中得有i出現，以及i和j的結果k出現，且最後的結果會是-1，有空再研究是否有更好的寫法。

Problem D. Ominous Omino

題意

現有一個R*C的格子中，現給你X-ominoes代表X個格子所能組成的方塊，請判斷RICHARD是否能找到其中一種方塊，讓GABRIEL不論接下來用哪種X-ominoes樣子的方塊都無法剛好填滿。

想法

當X大於七，一定會有中間為洞的方塊所以RICHARD一定贏，其它情況判斷是否整除，且把其它無法的例子找出。

心得

這題題目看了許久還是不知道正確的意思，送了16次的WA才知道原來是這樣，沒想到不符的規律，乾脆全列出來但還是漏掉了。

晚上還參加了TopCoder的資格賽，結果一題都沒寫出來 ..